package dp;

import java.util.ArrayList;
import java.util.List;

public class PalindromePartitioning131 {
    public List<List<String>> partition(String s) {
        boolean[][] dp = new boolean[s.length()][s.length()];
        //init
        for (int i = 0; i < s.length(); i++) {
            for (int j = 0; j < s.length(); j++) {
                if (i == j) {
                    dp[i][j] = true;
                } else {
                    dp[i][j] = false;
                }
            }
        }
        //dp赋值矩阵
        for (int i = 1; i < s.length(); i++) {
            for (int j = 0; j < s.length() - i; j++) {
                if (s.charAt(j) == s.charAt(j + i)) {
                    if (dp[j + 1][j + i - 1]||i==1) {
                        dp[j][j + i] = true;
                    }
                }
            }
        }

        List<List<String>> result = new ArrayList<>();
        //回溯枚举
        backtracing(0, s.length(), dp, result, new ArrayList<>(), s);
        return result;
    }

    private void backtracing(int index, int length, boolean[][] dp, List<List<String>> result, ArrayList<String> current, String s) {
        if (index == length) {
            result.add(new ArrayList<>(current));
            return;
        }
        for (int j = index; j < length; j++) {
            if (dp[index][j]) {
                current.add(s.substring(index, j + 1));
                backtracing(j + 1, length, dp, result, current, s);
                current.remove(current.size() - 1);
            }
        }

    }
}
